package com.chj.leetcode.tijie300to350;

public class Code322_CoinChange {
//	https://zhaonanli.gitbooks.io/leetcode/content/322coin-change.html
	public static int coinChange(int[] coins, int amount) {

		int inf = Integer.MAX_VALUE;
		int nums = coins.length;
		int[][] dp = new int[nums + 1][amount + 1];// dp[i][j]代表前i个***的钱加起来为j最少个数

		dp[0][0] = 0;
		for (int i = 1; i <= nums; i++) {
			dp[i][0] = 0;
		}
		for (int i = 1; i <= amount; i++) {
			dp[0][i] = inf;
		}

		for (int i = 1; i <= nums; i++) {
			for (int j = 1; j <= amount; j++) {
				dp[i][j] = inf;
				if (j < coins[i - 1]) {
					dp[i][j] = dp[i - 1][j];
				} else {
					if (dp[i][j - coins[i - 1]] != inf) {
						dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
					}
				}
			}
		}
		return dp[nums][amount] == inf ? -1 : dp[nums][amount];
	}

//	https://leetcode.com/problems/coin-change/discuss/141064/Unbounded-Knapsack
	public int coinChange02(int[] coins, int amount) {
		int n = coins.length;
		int[][] dp = new int[n][amount + 1];

		for (int i = 0; i < n; i++)
			for (int j = 0; j <= amount; j++)
				dp[i][j] = Integer.MAX_VALUE;

		// Populates the amount=0 columns, as we don't need any coin to make zero amount
		for (int i = 0; i < n; i++)
			dp[i][0] = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= amount; j++) {
				if (i > 0)
					dp[i][j] = dp[i - 1][j]; // Excludes the coin
				if (j >= coins[i]) {
					if (dp[i][j - coins[i]] != Integer.MAX_VALUE)
						dp[i][j] = Math.min(dp[i][j], dp[i][j - coins[i]] + 1); // Includes the coin
				}
			}
		}

		// total combinations will be at the bottom-right corner.
		return (dp[n - 1][amount] == Integer.MAX_VALUE ? -1 : dp[n - 1][amount]);
	}

//	https://zhaonanli.gitbooks.io/leetcode/content/322coin-change.html

	public int coinChange03(int[] coins, int amount) {
		if (coins.length == 0 || amount == 0) {
			return 0;
		}

		// DP formula:
		// f[i][amount] = min(f[i - 1][amount],
		// f[i][amount - k*[i]] + k)
		long[][] f = new long[coins.length + 1][amount + 1];
		// for (int i = 0; i <= coins.length; i ++) {
		// for (int a = 0; a <= amount; a ++) {
		// if (a == 0) {
		// f[i][a] = 0;
		// } else {
		// f[i][a] = (long)Integer.MAX_VALUE;
		// }
		// }
		// }

		f[0][0] = 0;
		for (int i = 1; i <= amount; i++) {
			f[0][i] = (long) Integer.MAX_VALUE;
		}

		for (int i = 1; i <= coins.length; i++) {
			f[i][0] = 0;
		}

		for (int i = 1; i <= coins.length; i++) {
			int currCoin = coins[i - 1];

			for (int j = 1; j <= amount; j++) {
				f[i][j] = f[i - 1][j];
				for (int k = 1; k * currCoin <= j; k++) {
					f[i][j] = Math.min(f[i][j], f[i][j - k * currCoin] + k);
				}
			}
		}

		return f[coins.length][amount] == Integer.MAX_VALUE ? -1 : (int) f[coins.length][amount];
	}

	public static void main(String[] args) {
		int[] arr = { 2 };
		int k = 3;
		System.out.println(coinChange(arr, k));
	}
}
